package com.github.yangyishe.p100;

import java.util.Arrays;

/**
 * 48. 旋转图像
 * https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
 *
 * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[[7,4,1],[8,5,2],[9,6,3]]
 * 示例 2：
 *
 *
 * 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
 * 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 *
 *
 * 提示：
 *
 * n == matrix.length == matrix[i].length
 * 1 <= n <= 20
 * -1000 <= matrix[i][j] <= 1000
 */
public class Problem48 {
    public static void main(String[] args) {
        int[][] matrix=new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,10,11,12},
                {13,14,15,16},
        };

        Problem48 problem48 = new Problem48();
        problem48.rotate(matrix);

        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }

    }

    /**
     * 思路:
     * 先仅考虑数学体系的情况. 每一行的位置从1到n
     * 矩阵一定会有一个中心点, 尽管中心点的位置可能不是整数
     * center=(1+n)/2
     *
     * 如果以中心点为原点, 则矩阵的每个位置, 会有一个新的坐标
     * 如对于n=3, 中心点为(2,2)
     * 则原来(1,1)的点, 以中心点为新原点的坐标就是(-1,-1)
     * 注: 此坐标体系与笛卡尔坐标体系的象限对应位置不是匹配的
     * 其经过顺时针90度后获取的新坐标是(-1,1)
     *
     * 对于n=4, 中心点为(2.5,2.5)
     * 则原来(1,2)的点, 新坐标为(-1.5,-0.5)
     * 旋转后, 新的坐标为(2,4)->(-0.5,1.5)
     *
     * 原来(2,4)->(-0.5,1.5)
     * 转换后为(4,3)->(1.5,0.5)
     *
     * 原来(4,3)->(1.5,0.5)
     * 转换为(3,1)->(0.5,-1.5)
     *
     * 新坐标规律为(row,col)->(col,-row)
     *
     * 据此, 分别写:
     * 1. 旧坐标转换新坐标
     * 2. 新坐标旋转
     * 3. 新坐标转换旧坐标
     * 即可把原来的一个点转换到90度后的新店.
     *
     * 而要批量处理所有点, 仅需写一个转换匹配4点的方法.
     * 再将前面((n+1)/2,n/2)的情况都旋转即可
     * 当n为偶数时, 处理row:1->n/2,col:1->n/2
     * 当n为奇数时, 处理row:1->(n+1)/2,col:1->(n-1)/2
     *
     *
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int n=matrix.length;
        for(int i=0;i<(n+1)/2;i++){
            for(int j=0;j<n/2;j++){
                rotateRepeatPoint(matrix,n,i,j);
            }
        }

    }

    public void rotateRepeatPoint(int[][] matrix,int n,int row,int col){
        // 此处待优化, 但不影响效率
        // 第1次
        int[] after = rotateOldPoint(new int[]{row, col}, n);
        int tempVal=matrix[after[0]][after[1]];
        matrix[after[0]][after[1]]=matrix[row][col];


        // 第2次
        int[] after2=rotateOldPoint(after,n);
        int tempVal2=matrix[after2[0]][after2[1]];
        matrix[after2[0]][after2[1]]=tempVal;

        // 第3次
        int[] after3=rotateOldPoint(after2,n);
        int tempVal3=matrix[after3[0]][after3[1]];
        matrix[after3[0]][after3[1]]=tempVal2;

        // 第4次
        int[] after4=rotateOldPoint(after3,n);
        matrix[after4[0]][after4[1]]=tempVal3;

    }

    /**
     * 旋转旧坐标, 获取旋转后的坐标
     * @param oldIndexs
     * @param n
     * @return
     */
    public int[] rotateOldPoint(int[] oldIndexs,int n){
        return new2Old(rotateNewPoint(old2New(oldIndexs,n)),n);
    }

    /**
     * 为支持小数, 使用2*关系表示新坐标
     *
     * newIndex=(oldIndex+1)*2-n-1
     *
     * @param oldIndexs
     * @param n
     * @return
     */
    public int[] old2New(int[] oldIndexs,int n){
        int oldRow = oldIndexs[0];
        int oldCol = oldIndexs[1];


        return new int[]{(oldRow+1)*2-n-1,(oldCol+1)*2-n-1};
    }

    public int[] rotateNewPoint(int[] newIndexs){
        return new int[]{newIndexs[1],-newIndexs[0]};
    }

    /**
     * oldIndex=(newIndex+n+1)/2-1
     * @param newIndexs
     * @param n
     * @return
     */
    public int[] new2Old(int[] newIndexs,int n){
        int newRow=newIndexs[0];
        int newCol=newIndexs[1];
        return new int[]{(newRow+n+1)/2-1,(newCol+n+1)/2-1};
    }
}
